With the rapid growth of the Internet, wide sharing of information and applications has become possible. However, with these opportunities, security has also become a major concern. For example, when connecting to the Internet, a private network may be exposed to over 50,000 unknown networks and all their users. Thus, confidential information on a private network may be exposed to unscrupulous parties when connected to a public network such as the Internet.
One type of common method used for obtaining confidential information is a replay attack. In a replay attack, an attacker copies confidential communications between two private parties. The attacker then replays the information to one or both of the parties in the hope that confidential information will be revealed, e.g., passwords or cryptographic keys.
A technique for protecting against a replay attack is to assign each packet a sequence number. For example, the Internet protocol security protocol (“IPsec”) and encapsulating security payload (“ESP”) protocol use a 32-bit sequence number assigned to each data packet. The sequence number is reset each time communications are established, e.g., during the setup of a security association. RFC-2401, R. Atkinson, the Internet Society (1998), titled “Security Architecture for IP,” describes, inter alia, IPsec and is incorporated herein by reference in its entirety. IPsec under RFC 2401 specifies that the window size for sequence checking must be a minimum of 32, and should be 64. Thus, IPSec permits packets to arrive out of order, e.g., up to 63 packets away from the highest-numbered packet yet received.
The typical causes of packets to arrive out of order include parallel processing paths inside routers or switches, traffic flows split among multiple links with differing delays, and routing “hiccups” where a flow shifts from one path to another with a different end-to-end delay. Changes in a route can easily induce changes in end-to-end delay of tens of milliseconds. For example, if the change involves a switch from a satellite link to a terrestrial one, the delay delta can even be in the 100 ms range. Unfortunately, these path-switching changes in end-to-end delay can significantly impact window-based sequence-checking algorithms such as those used by IPsec, especially in high-bandwidth flows.
Problems may arise when a flow's path changes from a route with a large end-to-end delay (possibly due to heavy congestion) to a route with a significantly smaller end-to-end delay. In this case, older packets from the prior route may continue to arrive long after newer packets arriving on the new route. Worse, in a high-bandwidth flow, there may be many packets in transit on both routes. For example, with a 100 Mb/s flow of 64-byte plaintext packets, a path with an end-to-end delay of 50 ms requires about 10,000 packets in flight. A decrease in path length of 5 ms would result in a 5 ms period of sequence number discontinuities affecting approximately 2000 packets (1000 packets on the old route intermixing with 1000 on the new route). Anti-replay algorithms must discriminate effectively between actual replay attacks and common network behaviors like path re-routing. This requires that the window size be based on reasonable expectations for packet re-ordering.
For window sizes of up to a few hundred bits, the RFC-2401 algorithm can make use of hardware parallelism to run in O(1) time using simple shift registers, or a large shift register combined with a few memory accesses. Unfortunately, the processing of sequence numbers, as currently described in RFC-2401 is inadequate, especially for high-bandwidth flows. For example, the RFC-2401 window slide algorithm requires O(N) operations, where N is the window size. Thus, the memory operations required under the window slide algorithm of RFC-2401 increases linearly based on window size. Furthermore, the algorithm described in RFC-2401 scales poorly in performance to larger window sizes required by such flows.